/// 题⽬4：实现⼀个算法，⽤于实现最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元。
/// 要求：输⼊是⾦额，输出最少的找零纸币数。⽐如输⼊24，输出最⼩找零纸币数：3(⼀张20元、两张2元)。(20)
/// 输⼊：24  
/// 输出：3
pub fn dp_rec_mc(amount: u32) -> u32 {
    let denominations: Vec<u32> = vec![1, 2, 5, 10, 20, 30, 50, 100];
    let mut dp = vec![None; (amount + 1) as usize]; // 初始化 DP 数组
    dp[0] = Some(0); // 0 元需要 0 张纸币

    for coin in denominations {
        for cur in coin..=amount {
            if let Some(i) = dp[(cur - coin) as usize] {
                dp[cur as usize] = Some(match dp[cur as usize] {
                    Some(j) => j.min(i + 1),
                    None => i + 1,
                })
            }
        }
    }

    dp[amount as usize].unwrap()
}
